Search results for "cellular automata"

One Alternation Can Be More Powerful Than Randomization in Small and Fast Two-Way Finite Automata

2013

We show a family of languages that can be recognized by a family of linear-size alternating one-way finite automata with one alternation but cannot be recognized by any family of polynomial-size bounded-error two-way probabilistic finite automata with the expected runtime bounded by a polynomial. In terms of finite automata complexity theory this means that neither 1Σ2 nor 1Π2 is contained in 2P2.

From deterministic cellular automata to coupled map lattices

2016

A general mathematical method is presented for the systematic construction of coupled map lattices (CMLs) out of deterministic cellular automata (CAs). The entire CA rule space is addressed by means of a universal map for CAs that we have recently derived and that is not dependent on any freely adjustable parameters. The CMLs thus constructed are termed real-valued deterministic cellular automata (RDCA) and encompass all deterministic CAs in rule space in the asymptotic limit $\kappa \to 0$ of a continuous parameter $\kappa$. Thus, RDCAs generalize CAs in such a way that they constitute CMLs when $\kappa$ is finite and nonvanishing. In the limit $\kappa \to \infty$ all RDCAs are shown to ex…

Semipredictable dynamical systems

2015

A new class of deterministic dynamical systems, termed semipredictable dynamical systems, is presented. The spatiotemporal evolution of these systems have both predictable and unpredictable traits, as found in natural complex systems. We prove a general result: The dynamics of any deterministic nonlinear cellular automaton (CA) with $p$ possible dynamical states can be decomposed at each instant of time in a superposition of $N$ layers involving $p_{0}$, $p_{1}$,... $p_{N-1}$ dynamical states each, where the $p_{k\in \mathbb{N}}$, $k \in [0, N-1]$ are divisors of $p$. If the divisors coincide with the prime factors of $p$ this decomposition is unique. Conversely, we also prove that $N$ CA w…

Automata and forbidden words

1998

Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.

Modeling the shrub and juniper encroachment in the western north America grasslands with a Cellular Automata model

2013

Analysing urban development with decision tree based cellular automata. Toward an automatic transition rule creation process.

2016

International audience

On the Hierarchy Classes of Finite Ultrametric Automata

2015

This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any k-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite k-head automata is a proper subclass of the class of languages recognized by (k + 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines an…

Varieties Generated by Certain Models of Reversible Finite Automata

2006

Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models.

Cellular automaton for chimera states

2016

A minimalistic model for chimera states is presented. The model is a cellular automaton (CA) which depends on only one adjustable parameter, the range of the nonlocal coupling, and is built from elementary cellular automata and the majority (voting) rule. This suggests the universality of chimera-like behavior from a new point of view: Already simple CA rules based on the majority rule exhibit this behavior. After a short transient, we find chimera states for arbitrary initial conditions, the system spontaneously splitting into stable domains separated by static boundaries, ones synchronously oscillating and the others incoherent. When the coupling range is local, nontrivial coherent struct…

Can the Double Exchange Cause Antiferromagnetic Spin Alignment?

2020

The effect of the double exchange in a square-planar mixed-valence dn+1&minus